package Year22_Month06.day18;

public class 从中序与后序遍历序列构造二叉树 {
    int index;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        index = postorder.length - 1;
        //这里特别说明一下，你传入的inright的值，是根据你的判断条件来确定的，影响最大的就是你的中间的值
        return rebuildTree(inorder,postorder,0,inorder.length);
    }

    public TreeNode rebuildTree(int[] inorder, int[] postorder,int inleft,int inright){
        if(index < 0 || inleft >= inright) return null;

        //开始进行根节点的查找
        int pos = inleft;
        while(pos < inright){
            if(inorder[pos] == postorder[index]) break;
            pos++;
        }

        //开始进行根节点的构造
        int nodeVal = postorder[index];
        index--;
        TreeNode root = new TreeNode(nodeVal);
        //注意：这里的树的递归是根据后序遍历来确定的，左-->右-->根，所以根节点确定之后，是要先搞右子树的。
        root.right = rebuildTree(inorder,postorder,pos+1,inright);
        root.left = rebuildTree(inorder,postorder,inleft,pos);
        return root;
    }
}
